package com.kitty.record.kittyalgorithm.audition;

import sun.util.resources.cldr.shi.CalendarData_shi_Latn_MA;

import javax.swing.plaf.ListUI;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。
 * 换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
 * 示例 1：
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
 * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * <p>
 * 示例 2： 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 * 输出：Reference of the node with value = 2
 * 解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为[3,2,4]。
 * 在 A 中，相交节点前有 3 个节点；
 * 在 B 中，相交节点前有 1 个节点。
 * <p>
 * 示例 3： 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 * 输出：null
 * 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
 * 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
 * 解释：
 * 这两个链表不相交，因此返回 null。
 * <p>
 * 注意： 如果两个链表没有交点，返回 null 。 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。
 * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 Related Topics 链表
 *
 * @Author SHEN
 * @Date 2020/11/26
 */
public class LeetCode0207 {
    public static void main(String[] args) {
        //[4,1,8,4,5]
        int[] l = {4, 1, 8, 4, 5};
        ListNode init = init(l);
    }

    public static ListNode init(int[] l) {
        ListNode a = new ListNode(l[0]);
        for (int i = 1; i < l.length; i++) {
        }
        return a;
    }


    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();

        //将a链表加入到set集合
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            //判断set集合存不存在，存在的话就返回
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        //获取链表长度
        int lA = length(headA);
        int lB = length(headB);


        //遍历两个链表使其长度一样
        while (lA != lB) {
            if (lA > lB) {
                headA = headA.next;
                lA--;
            }
            if (lA < lB) {
                headB = headB.next;
                lB--;
            }
        }

        //从两个链表相同的位置遍历，当链表一样时返回链表；
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;

    }

    public static int length(ListNode node) {
        int l = 0;
        while (node != null) {
            l++;
            node = node.next;
        }
        return l;
    }


    public static ListNode getIntersectionNode3(ListNode headA, ListNode headB) {

        ListNode tempA = headA;
        ListNode tempB = headB;

        while (tempA != tempB) {
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }

        return tempA;
    }


    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    ListNode head = null;
    //链表头添加
    public void addHead(int data) {
        ListNode node = new ListNode(data);
        node.next =head;
        head =node;
    }
    //打印
    public void printLink() {
        ListNode curNode = head;
        while(curNode !=null) {
            System.out.println(curNode.val+" ");
            curNode = curNode.next;
        }
        System.out.println();
    }

    //长度
    public int length() {
        int length =0;
        ListNode curr = head;
        while(curr!=null) {
            length++;
            curr=curr.next;
        }
        return length;
    }

    //在尾部插入
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head==null) {
            head = node;
        }
        else {
            ListNode temp =head;
            while(temp.next!=null) {
                temp =temp.next;
            }
            temp.next=node;
        }

    }

    //按照索引删除
    public void deleteByIndex(int index) {
        ListNode temp = head;
        if (index < 0 || index > length()) {
            System.out.println("位置不对");
            return;
        } else if (index == 0) {
            head = head.next;
        } else {
            for (int i = 1; i < index; i++) {
                temp = temp.next;
            }
            temp.next = temp.next.next;
        }
    }
}
